package com.yiwenup.sorting._03_heap;

import com.yiwenup.sorting.base.Sort;

/**
 * 堆排序
 * 时间复杂度：O(nlogn)
 * 空间复杂度：O(1)
 * 稳定性：不稳定
 **/
public class HeapSort<E extends Comparable<E>> extends Sort<E> {
    private int heapSize;

    @Override
    protected void work() {
        // 原地建堆
        heapSize = array.length;
        for (int i = (heapSize >> 1) - 1; i >= 0 ; i--) {
            siftDown(i);
        }

        while (heapSize > 1) {
            // 交换堆顶元素的位置
            swap(0, --heapSize);
            // 0位置下滤，保证堆的性质
            siftDown(0);
        }
    }

    /**
     * 下滤
     */
    private void siftDown(int idx) {
        E element = array[idx];

        int half = heapSize >> 1;
        while (idx < half) {
            // 默认去左子节点
            int childIdx = (idx << 1) + 1;
            E child = array[childIdx];

            int rightIdx = childIdx + 1;
            if (rightIdx < heapSize && cmp(array[rightIdx], child) > 0) {
                child = array[childIdx = rightIdx];
            }

            if (cmp(element, child) >= 0) break;

            array[idx] = child;
            idx = childIdx;
        }
        array[idx] = element;
    }
}
